Most problems encountered in engineering design are nonlinear by nature and involve the determination of system parameters that satisfy certain goals for the problem being solved. Such problems can be cast in the form of a mathematical optimization problem where a solution is desired that minimizes a system function or parameter subject to limitations or constraints on the system. Both the system function and constraints are comprised of system inputs (control variables) and system outputs, which may be either discrete or continuous. Furthermore, constraints may be equalities or inequalities. The solution to a given optimization problem has either or both of the following characteristics: 1) minimizes or maximizes a desired condition or conditions, thus satisfying the optimality condition and 2) satisfies the set of constraint equations imposed on the system.
With the above definitions, several categories of optimization problems may be defined. A Free Optimization Problem (FOP) is one for which no constraints exist. A Constraint Optimization Problem (COP) includes both constraints and a minimize (or maximize) condition(s) requirement. In contrast, a Constraint Satisfaction Problem (CSP) contains only constraints. Solving a CSP means finding one feasible solution within the search space that satisfies the constraint conditions. Solving a COP means finding a solution that is both feasible and optimal in the sense that a minimum (or maximum) value for the desired condition(s) is realized.
The solution to such a problem typically involves a mathematical search algorithm, whereby successively improved solutions are obtained over the course of a number of algorithm iterations. Each iteration, which can be thought of as a proposed solution, results in improvement of an objective function. An objective function is a mathematical expression having parameter values of a proposed solution as inputs. The objective function produces a figure of merit for the proposed solution. Comparison of objective function values provides a measure as to the relative strength of one solution versus another. Numerous search algorithms exist and differ in the manner by which the control variables for a particular problem are modified, whether a population of solutions or a single solution is tracked during the improvement process, and the assessment of convergence. However, these search algorithms rely on the results of an objective function in deciding a path of convergence. Examples of optimization algorithms include Genetic Algorithms, Simulated Annealing, and Tabu Search.
Within optimization algorithms, the critical issue of handling constraints for COPs and CSPs must be addressed. Several classes of methods exist for dealing with constraints. The most widespread method is the use of the penalty approach for modifying the objective function, which has the effect of converting a COP or CSP into a FOP. In this method, a penalty function, representing violations in the set of constraint equations, is added to an objective function characterizing the desired optimal condition. When the penalty function is positive, the solution is infeasible. When the penalty function is zero, all constraints are satisfied. Minimizing the modified objective function thus seeks not only optimality but also satisfaction of the constraints.
For a given optimization search, the penalty approach broadens the search space by allowing examination of both feasible and infeasible solutions in an unbiased manner. Broadening the search space during an optimization search often allows local minima to be circumnavigated more readily, thus making for a more effective optimization algorithm. In contrast, alternate methods for handling constraints, such as infeasible solution ‘repair’ and ‘behavioral memory’, are based on maintaining or forcing feasibility among solutions that are examined during the optimization search.
To implement the penalty approach, a mathematical expression is defined for each constraint that quantifies the magnitude of the constraint violation. For the given constraint, a weighting factor then multiplies the result to create an objective function penalty component. Summing all penalty components yields the total penalty. The larger the weighting factor for a given constraint, the greater the emphasis the optimization search will place on resolving violations in the constraint during the optimization search. Many approaches exist for defining the form of the penalty function and the weighting factors. As defined by the resultant modified objective function, weighting factors are problem specific and are bounded by zero (the constraint is not active) and infinity (the search space omits all violations of the constraint).
The simplest penalty function form is the ‘death penalty’, which sets the value of the weighting factor for each constraint to infinity. With a death penalty the search algorithm will immediately reject any violation of a constraint, which is equivalent to rejecting all infeasible solutions. Static penalties apply a finite penalty value to each constraint defined. A static weighting factor maintains its initial input value throughout the optimization search. Dynamic penalties adjust the initial input value during the course of the optimization search according to a mathematical expression that determines the amount and frequency of the weight change. The form of the penalty functions in a dynamic penalty scheme contains, in addition to the initial static penalty weighting factors (required to start the search), additional parameters that must be input as part of the optimization algorithm.
Similar to dynamic penalties, adaptive penalties adjust weight values over the course of an optimization search. In contrast, the amount and frequency of the weight change is determined by the progress of the optimization search in finding improved solutions. Several approaches for implementing adaptive penalty functions have been proposed. Bean and Hadj-Alouane created the method of Adaptive Penalties (AP), which was implemented in the context of a Genetic Algorithm. In the AP method, the population of solutions obtained over a preset number of iterations of the optimization search is examined and the weights adjusted depending on whether the population contains only feasible, infeasible, or a mixture of feasible and infeasible solutions. Coit, Smith, and Tate proposed an adaptive penalty method based on estimating a ‘Near Feasibility Threshold’ (NFT) for each given constraint. Conceptually, the NFT defines a region of infeasible search space just outside of feasibility that the optimization search would then be permitted to explore. Eiben and Hemert developed the Stepwise Adaption of Weights (SAW) method for adapting penalties. In their method, a weighting factor adjustment is made periodically to each constraint that violates in the best solution, thus potentially biasing future solutions away from constraint violations.
Several deficiencies exist in the penalty methods proposed. Death penalties restrict the search space by forcing all candidate solutions generated during the search to satisfy feasibility. In the static weighting factor approach, one must perform parametric studies on a set of test problems that are reflective of the types of optimization applications one would expect to encounter, with the result being a range of acceptable weight values established for each constraint of interest. The user would then select the weight values for a specific set of constraints based on a pre-established range of acceptable values. Particularly for COPs, varying the static weight values for a given problem can often result in a more or less optimal result. Similarly, dynamic penalties require the specification of parameters that must be determined based on empirical data. Fine-tuning of such parameters will often result in a different optimal result.
Penalty adaption improves over the static and dynamic penalty approaches by attempting to utilize information about the specific problem being solved as the optimization search progresses. In effect, the problem is periodically redefined. A deficiency with the adaptive penalty approach is that the objective function loses all meaning in an absolute sense during the course of an optimization search. In other words, there is no ‘memory’ that ties the objective function back to the original starting point of the optimization search as exists in a static penalty or dynamic penalty approach.